// Copyright (C) 2011  Andrew H. Chan
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
// 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

#ifndef _BLOCKBWT_HPP__
#define _BLOCKBWT_HPP__

#include <iostream>
#include <vector>
#include <cstdlib>
#include <assert.h>

#include "ntSeq.hpp"
#include "differenceCoverSample.hpp"

#define INDEX_PERIOD 32

typedef unsigned long long uint64;

class BWT {
    public:
        BWT(ntSeq const &T, uint64 logv, uint64 numSplitters);

        std::vector<uint64> generateSplitters(ntSeq const &T, DCS const &dcs, uint64 numSplitters) const;
        std::vector<uint64> precomputePP(ntSeq const &T, uint64 v, uint64 pp) const;
        std::vector<uint64> smallerSuffixes(ntSeq const &T, DCS const &dcs, uint64 pp) const;
        int verifySmallerSuffixes(ntSeq const &T, uint64 pp, std::vector<uint64> const &smaller) const;
        std::vector<uint64> largerEqSuffixes(ntSeq const &T, DCS const &dcs, uint64 pp) const;
        int verifyLargerEqSuffixes(ntSeq const &T, uint64 pp, std::vector<uint64> const &larger) const;
        std::vector<uint64> betweenSuffixes(ntSeq const &T, DCS const &dcs, uint64 splitter1, uint64 splitter2) const;
        int verifyBetweenSuffixes(ntSeq const &T, uint64 splitter1, uint64 splitter2, std::vector<uint64> const &betweenSuf) const;
        void multiQsort(ntSeq const &T, DCS const &dcs, std::vector<uint64> &suffixes, uint64 charIndex, uint64 index, uint64 length) const;
        void qsortDCS(ntSeq const &T, DCS const &dcs, std::vector<uint64> &suffixes, uint64 index, uint64 length) const;
        int verifyQsort(ntSeq const &T, std::vector<uint64> const &suffixes) const;

        inline uint64 getOcc(uint64 bwtIndex);
        inline uint64 stepLeft(uint64 bwtIndex);
        std::vector<uchar> unpermute();

        // fields
        uint64 n;
        ntSeq bwt;
        uint64 term; // position of terminating character in bwt
        uint64 C[4]; // cumulative character counts
        std::vector<uint64> occ[4]; // sparse occurrence counts
        std::vector<uint64> pos; // sparse positions
};

#endif
